Leetcode 438.找到字符串中所有字母异位词

题目描述：

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指字母相同，但排列不同的字符串。

示例 1:

1
2
3
4
5

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

1
2
3
4
5
6

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

• $1 <= s.length, p.length <= 3 * 10^4$
• s 和 p 仅包含小写字母

链接：

https://leetcode-cn.com/problems/find-all-anagrams-in-a-string

题目分析

  刚阅读题目的时候以为异位词必须满足排列不同，那排除排列完全相同的情况还是有点麻烦的，后面观察示例发现排列完全相同也算在异位词里面，那就好办了。这道题有点像 Leetcode 76.最小覆盖子串，我们知道异位词首先需要满足的是长度相同，那么可以使用滑动窗口的思想，而这个窗口的大小是固定的，就是 p 的长度。异位词只需要满足字母相同，那么我们可以使用一个哈希表来记录 p 中各个字母的数量，作为我们的目标 target。
  在那道题中，我们使用了另外一个哈希表来记录窗口中的各字母数量并将其与 target 进行比对，在这道题中我们要寻找的是字母完全相同的子串而不是能够覆盖的子串，那么可以不使用另外一个哈希表，而是直接对 target 进行操作。进入窗口的每个数我们直接将 target 中对应的值减 1，视为“匹配目标”，这样当 target 中所有的值都为 0 的时候也就意味着当前窗口的字母与 p 完全相同。而移出窗口则加 1，也就是“退出匹配”。
  开始时先将与 p 长度相同的字符加入窗口，成为初始窗口。窗口进行滑动的时候，将右边的一个字符加入窗口，左边一个字符移出窗口即可。对于每一个窗口，我们都判断 target 的所有值是不是都变成了 0，是则说明当前窗口是一个异位词，将窗口的起点索引加入结果数组。
  需要注意的细节是，p 的长度如果比 s 大是一定不满足的，可以返回空数组。然后移动窗口的时候不要越界，也就是最后一个窗口判断后不能再继续右移了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        if(s.size() < p.size()) return result;
        unordered_map<char, int> target;
        int len = p.size();
        for(const char ch : p){
            target[ch]++;
        }
        for(int i = 0; i < len; i++){
            target[s[i]]--;
        }
        for(int i = 0; i <= s.size() - len; i++){
            bool flag = true;   // 判断是否全为 0
            for(const auto& it : target){
                if(it.second != 0){
                    flag = false;
                    break;
                }
            }
            if(flag){
                result.emplace_back(i);
            }
            if(i != s.size() - len){
                target[s[i]]++;     // 左边移出窗口
                target[s[i+len]]--; // 右边移入窗口
            }
        }
        return result;
    }
};

  时间复杂度：$O(|\alpha|\times n)$，其中 $n$ 是 s 的长度，$|\alpha|$ 是哈希表的大小，在这里不超过 26。我们进行窗口滑动相当于对字符串 s 进行了一次遍历，而每一个窗口都需要遍历哈希表判断是否值全为 0。题目中说明了字符串中仅包含小写字母，也就是不超过 26 个字符。
  空间复杂度：$O(|\alpha|)$。也即哈希表的大小。而作为结果输出的数组不计入空间复杂度中。